package cn.xiaolang.function.sort_algorithm;

/**
 * 希尔排序
 * 
 * @author fuhw/DeanKano
 * @date 2018-11-28
 */
public class ShellSort extends AbstractSort {

	/**
	 * 1.将整个待排序的序列,按照指定gap=3步长,分成若干个子序列
	 * 2.对若干个子序列分别进行直接插入排序
	 * 3.待整个序列待记录“基本有序”(gapLen=1),再对全体记录进行一次直接插入排序
	 */
	@Override
	public void sort(int[] a) {
		int arrLen = a.length;
		int gap = 3;// 步长（大于1的值）
		int gapLen = 1;//特定步长下要循环对元素长度
		while (gapLen < arrLen / gap) {
			gapLen = gap * gapLen + 1;
		}
		while (gapLen >= 1) {
			for (int i = 0; i < gapLen; i++) {// 分组
				for (int j = i + gapLen; j < a.length; j += gapLen) {// 元素从第二个开始
					int k = j - gapLen;// k为有序序列最后一位的位数
					int temp = a[j];// 要插入的元素
					while (k >= 0 && temp < a[k]) {// 从后往前遍历
						a[k + gapLen] = a[k];
						k -= gapLen;// 向后移动len位
					}
					a[k + gapLen] = temp;
				}
			}
			// 若干个子序列分别进行直接插入排序完后，再对全体记录进行一次直接插入排序
			gapLen = gapLen / gap;
		}
	}
}
